home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 17646 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: galaxy.ucr.edu!not-for-mail
  2. From: thp@cs.ucr.edu (Tom Payne)
  3. Newsgroups: comp.lang.java,comp.lang.c++,comp.lang.smalltalk
  4. Subject: Re: Will Java kill C++?
  5. Followup-To: comp.lang.java,comp.lang.c++,comp.lang.smalltalk
  6. Date: 16 Apr 1996 23:05:50 GMT
  7. Organization: University of California, Riverside
  8. Message-ID: <4l194e$q11@galaxy.ucr.edu>
  9. References: <3134D499.653E@ix.netcom.com> <313613B2.136E@ksopk.sprint.com> <4i7qhl$ik6@cronkite.seas.gwu.edu> <4iuhi7$fmf@sundog.tiac.net> <4iumap$mn5@hustle.rahul.net> <31582A45.3742@vmark.com> <3163C031.4FB1@esec.ch> <3164888D.2B01@concentric.net> <4kbfn8$1bu@news1.is.net> <4kqjf6$kh0@kaiwan009.kaiwan.com> <317173F1.5790@concentric.net>
  10. NNTP-Posting-Host: corvette.ucr.edu
  11. X-Newsreader: TIN [UNIX 1.3 950824BETA PL0]
  12.  
  13. Alan L. Lovejoy (alovejoy@concentric.net) wrote:
  14. : 
  15. : I did those benchmars to prove that Smalltalk message sends are faster
  16. : than c function calls.  To do that, I needed a benchmark that consisted
  17.  
  18. How is that possible, given that the message has to find the entry
  19. point of the method and has to communicate parameters by mechanisms
  20. not unavailable to C.
  21.  
  22. : mostly of function calls/message sends--and involved as little other
  23. : code as possible.  The recursive factorial and fibonacci functions
  24. : meet those requirements better than anything else I could think of.
  25. : 
  26. : To do any better, you'd need a completely synthetic benchmark.
  27.  
  28. So, compute the number p(n,k) of ways of writing n as the sum of k
  29. positive numbers (irrespective of ordering), i.e., the number of k-way
  30. partitions of n.  The recursion formula is
  31.  
  32.       p(n,k)  =  p( n-1, k-1 )  +  p( n-k, k )
  33.  
  34. i.e., the number of partitions that involve a 1 plus the number that
  35. don't involve a 1.  The boundary conditions are that 
  36.    
  37.       p(n,k) = 1 whenever k is 1 or n  
  38.  
  39. and
  40.  
  41.       p(n,k) = 0 whenver k is less than one or greater than n.
  42.  
  43. The beauty of this application of recursion is that each call
  44. generates two more, without the numbers growing so fast as with
  45. factorial and/or fibonacci (which tend to overflow before 
  46. generating an interesting amount of work).
  47.  
  48. Tom Payne (thp@cs.ucr.edu)
  49.